道路建设
题意:
给你$n$个农场的坐标,给出$m$条已经存在的路(连接农场$i$与农场$j$),求最少要修建多长的路才能把所有农场连接起来。
上面的太啰嗦了,再简化一下:
给你$n$个节点,给出$m$条权值为0的边,每个节点彼此有一条边连接,边权值为两点的欧几里得距离,求该图的最小生成树大小。
欧几里得距离公式:$dis=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$
这道题我是用$Prim$做的,感觉$Prim$更好些,1000个点100条边算稀疏图吧
一定要注意在计算欧几里得距离时要在$sqrt()$里加double,不然就会卡精度WA2个点 (别问我怎么知道的)
代码解析:
1 |
|